package com.itheima.leetcode.od.b.graph.bipartitegraph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <h3>素数伴侣</h3>
 * 若两个正整数的和为素数，则这两个正整数称之为"素数伴佀"，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N (N 为偶数)个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数:2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣"，能组成“素数伴侣"最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
 * 有一个正偶数n，表示待挑选的自然数的个数。后面给出n个具体的数字。
 * 输出一个整数K，表示你求得的“最佳方案"组成“素数伴侣"的对数。
 * 数据范围：1 ≤ n ≤ 100，输入的数据大小满足： 2 ≤ val ≤ 30000
 * <p>
 * 输入描述：
 * <p>
 * 第一行输入一个正偶数 n
 * <p>
 * 第二行输入n个整数，空格分隔
 * <p>
 * 输出描述：
 * <p>
 * 求得的“最佳方案"组成"素数伴侣”的对数。
 * <p>
 * 示例1：
 * <p>
 * 输入：
 * <p>
 * 4
 * <p>
 * 2 5 6 13
 * <p>
 * 输出：
 * <p>
 * 2
 * <p>
 * 说明：
 * <p>
 * 2和5的和为7，是素数。
 * <p>
 * 6和13的和为19，也是素数。
 * <p>
 * 所以可以组成两个“素数伴侣”对，输出结果是2。
 * <p>
 * 示例2：
 * <p>
 * 输入：
 * <p>
 * 6
 * <p>
 * 1 4 5 6 10 11
 * <p>
 * 输出：
 * <p>
 * 2
 * <p>
 * 说明：
 * <p>
 * 1和6的和为7，是素数。
 * <p>
 * 5和6的和为11，也是素数。
 * <p>
 * 所以可以组成两个“素数伴侣”对，输出结果是2。
 */
public class PrimeNumberCompanion {
    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);

        // 读取输入
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 计算并输出结果
        System.out.println(maxPrimePairs(nums));

        scanner.close();*/

        int n = 4;
        String input = "2 5 6 13";
        int[] nums = Arrays.stream(input.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        // 计算并输出结果
        System.out.println(maxPrimePairs(nums));
    }

    /**
     * 求解最大素数伴侣对数
     *
     * @param nums
     * @return
     */
    private static int maxPrimePairs(int[] nums) {
        List<Integer> oddNums = new ArrayList<>();
        List<Integer> evenNums = new ArrayList<>();

        // 分离奇偶数
        for (int num : nums) {
            if (num % 2 == 1) {
                oddNums.add(num);
            } else {
                evenNums.add(num);
            }
        }

        int[] matches = new int[oddNums.size()];
        Arrays.fill(matches, -1);
        int count = 0;

        // 对每个偶数尝试寻找匹配
        for (int i = 0; i < evenNums.size(); i++) {
            boolean[] used = new boolean[oddNums.size()];
            if (findMatch(i, used, matches, oddNums, evenNums)) {
                count++;
            }
        }

        return count;
    }

    /**
     * 匈牙利算法寻找匹配
     * <p>
     * 关于二分图可以参考这些视频：
     * <p>
     * <a href="https://blog.csdn.net/u013384984/article/details/90718287">匈牙利算法</a>
     * <p>
     * <a href="https://blog.csdn.net/zack_liu/article/details/123396889">匈牙利算法及KM算法详解</a>
     *
     * @param evenNum
     * @param used
     * @param matches
     * @param oddNums
     * @param evenNums
     * @return
     */
    private static boolean findMatch(int evenNum, boolean[] used, int[] matches,
                                     List<Integer> oddNums, List<Integer> evenNums) {
        for (int i = 0; i < oddNums.size(); i++) {
            if (!used[i] && isPrime(oddNums.get(i) + evenNums.get(evenNum))) {
                used[i] = true;
                if (matches[i] == -1 || findMatch(matches[i], used, matches, oddNums, evenNums)) {
                    matches[i] = evenNum;
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 判断是否为素数
     *
     * @param n
     * @return
     */
    private static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n)/*开方*/; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}